1. Field of the Invention
This invention relates to error detection and/or correction and particularly to generating an error code by multiplying the input data word by a matrix of "1"s and "0"s conforming to the mathematical expression of a predetermined error detection and/or correction code algorithm.
2. Description of the Prior Art
It has been widely recognized that error detection and/or correction is desirable in situations where an input binary word is operated upon in a manner having a significant probability of inadvertent alteration of at least one of the bits. Accordingly, it is common in systems requiring data transmission/reception or data recording/retrieval to incorporate an error detection and/or correction scheme selected to provide a desired level of detection at an acceptable cost. For example, simple parity check techniques are generally satisfactory in situations where six to eight bits form the word that is to be transmitted or received, stored or read from storage. More sophisticated techniques have found use in systems which involve relatively long binary words or blocks of information. Polynomial or cyclic redundancy code (CRC) techniques have been found to be useful--see U.S. Application Ser. No. 91,681 filed Nov. 5, 1979, now U.S. Pat. No. 4,276,646 issued 6/30/81, entitled "Method and Apparatus for Detecting Errors in a Data Set" to Haggard et al and assigned to the assignee of this invention.
Systematic codes have also been found to be useful in error correction and/or detection. The basis for the code used in this invention is described in detail in the Bell System Technical Journal Volume XXIX, Apr. 1950, No. 2 entitled "Error Detecting and Error Correcting Codes" by R. W. Hamming. This code has been used extensively over the years in connection with relatively short binary words. For example, a sixteen bit input word requires a six bit Hamming code to provide a capability of detecting two errors and correcting one within that sixteen bit word. In the past, the generation of the code has been accomplished through the use of exclusive OR circuits. When, as in the present invention, a large word such as 512 bits is to have a capability of two bit error detection and one bit correction, a code of eleven bits is required. The prior art exclusive OR circuitry would be prohibitively complex and expensive to generate these eleven bits.
In accordance with this invention, matrices made up of "1"s and "0"s conforming to the mathematical expression of the Hamming code are multiplied by each of the 64 bytes making up the 512 bit word.